package com.gyg.程序员面试金典;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */

import java.util.HashSet;
import java.util.Set;

/**
 * 面试题 02.01. 移除重复节点
 */
public class T02_01 {
    /**
     * 使用缓存区
     * @param head
     * @return
     */
    public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null){
            return null;
        }
        Set<Integer> listNodeSet = new HashSet<Integer>();
        ListNode firsyListNode = new ListNode(-1);
        firsyListNode.next = head;
        ListNode pre = firsyListNode;
        while (pre.next != null){
            if (!listNodeSet.contains(pre.next.val)){
                listNodeSet.add(pre.next.val);
                pre = pre.next;
            }else {
                pre.next = pre.next.next;
            }
        }
        return firsyListNode.next;
    }

    /**
     * 优化 不使用缓存区
     * @param head
     * @return
     */
    public ListNode removeDuplicateNodes_2(ListNode head) {
        ListNode temp1 = head;
        while (temp1 != null){
            ListNode temp2 = temp1;
            while (temp2.next != null){
                if (temp2.next.val == temp1.val){
                    temp2.next = temp2.next.next;
                }else {
                    temp2 = temp2.next;
                }
            }
            temp1 = temp1.next;
        }
        return head;
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
    }

}

